package demo1;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 *     //key -> 通过某种方法 -> 一次定位到这个数据的位置 --- hash表
 *     //hash冲突: 不同的关键字key,通过相同的哈希函数得到了相同的值,这个现象被称为 "哈希冲突/哈希碰撞"
 *     //hash冲突一定会发生,不可避免.我们应该尽量降低hash冲突
 *     //解决方法:
 *     // 1.线性探测 : 放到不为空的地方
 *     // 2.二次探测 : 通过公式H(i)= (H0 + i^2)%m 计算,放到不同的位置
 *     // java 解决hash冲突多采用 <开散列/哈希桶> : 数组+链表
 * User: wx
 * Date: 2024-05-03
 * Time: 16:11
 */
public class HashBuck {

    static class Node{
        public int key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    public Node[] array;
    public int usedSize;

    public static float DEFAULT_LOAD_FACTOR = 0.75f;
    public HashBuck() {
        array = new Node[10];
    }
    public void put(int key, int val) {
        int index = key % array.length;

        //遍历index下标的链表 是否存在 key 存在就更新value 不存在 进行头插法 插入数据

        Node cur = array[index];
        while(cur != null) {
            if (cur.key == key) {
                cur.val = val;
            }
            cur = cur.next;
        }
        //遍历完成 没有找到key
        //头插法进行插入
        Node node = new Node(key,val);
        node.next = array[index];
        array[index] = node;
        usedSize++;//8

        if (doLoadFactor() > DEFAULT_LOAD_FACTOR) {
            //扩容
            //array = Arrays.copyOf(array,2*array.length);
            //为什么这种扩容会出现错误的?
            //扩容后需要重新进行hash,因为长度已经改变,原来位置冲突的元素,可能要放到
            //新的数组的其他位置去
            resize();
        }
    }

    private void resize() {
        Node[] newArray = new Node[2*array.length];

        //遍历原来的数组
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            //遍历每个数组元素(链表)
            while(cur != null){
                Node tmp = cur.next;
                int newIndex = cur.key % newArray.length;//新的数组下标
                //采用头插法,插入到新数组的 newIndex 下标
                cur.next = newArray[newIndex];
                newArray[newIndex] = cur;
                //cur = cur.next; 会丢失下标,所以需要做一个标记
                cur = tmp;
            }
        }
        array = newArray;
    }
    public int get(int key) {
        //先存一个下标
        int index = key % array.length;
        //根据下标遍历这个节点
        Node cur = array[index];
        while(cur != null) {
            if (cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }
    private float doLoadFactor() {
        return usedSize * 0.1f / array.length;
    }
}
